/**
 * 伪随机数生成器模块
 * License: BSD
 * Authors: Lucifer (786325481@QQ.com)
 * Copyright: Copyright (C) 2008 Lucifer. All rights reserved.
 */
module system.Random;

import system.Exception;

version(Windows)
{
    private extern(Windows) uint GetTickCount();
}

/**
 * 表示伪随机数生成器，一种能够产生满足某些随机性统计要求的数字序列的设备。
 */
public class Random
{
    private const int MBIG = int.max;
    private const int MSEED = 161803398;
    private const int MZ = 0;

    private int inext, inextp;
    private int[56] SeedArray;
    /** 使用与时间相关的默认种子值，初始化 Random 类的新实例。*/
    /**
     * Comments: 生成的数字分布均匀；每个数字返回的可能性均相等。
     *           默认种子值是从系统时钟派生而来的。
     *           但是，在高性能系统上生成随机数时，系统时钟值可能不会产生预期的行为。
     *           当前实现采用Donald E. Knuth 的减法随机数生成器算法，更多信息请参考
	 *           “The Art of Computer Programming, volume 2: Seminumerical Algorithms” & “Numerical Recipes in C(Second)”。
     */
    this ()
    {
        version(Windows)
        {
            this(cast(int)GetTickCount());
        }
        version(linux)
        {
            static assert(false, "Not implemented in linux.");
        }
    }
    /** 使用指定的种子值初始化 Random 类的新实例。*/
    /** Params: Seed = 用来计算伪随机数序列起始值的数字。
     *          如果指定的是负数，则使用其绝对值。
     */
    this (int Seed)
    {
        int ii;
        int mj, mk;

        if(Seed == int.min)
        {
            throw new OverflowException("Negating the minimum value of a twos complement number is invalid.");
        }
        Seed = Seed >= 0 ? Seed : -Seed;

        // Numerical Recipes in C online @ http://www.library.cornell.edu/nr/bookcpdf/c7-1.pdf
        mj = MSEED - Seed;
        SeedArray [55] = mj;
        mk = 1;
        for (int i = 1; i < 55; i++)
        {  //  [1, 55] is special (Knuth)
            ii = (21 * i) % 55;
            SeedArray [ii] = mk;
            mk = mj - mk;
            if (mk < 0) mk += MBIG;
            mj = SeedArray [ii];
        }
        for (int k = 1; k < 5; k++)
        {
            for (int i = 1; i < 56; i++)
            {
                SeedArray [i] -= SeedArray [1 + (i + 30) % 55];
                if (SeedArray [i] < 0)
                    SeedArray [i] += MBIG;
            }
        }
        inext = 0;
        inextp = 31;    //31 is special(Knuth)
    }
    /**
     * 返回一个介于 0.0 和 1.0 之间的随机数。
     * Comments: 创建 Random 的派生类以重写此方法并产生另一种分布
     */
    protected double sample ()
	{
		int retVal;
		//增量inext, inextp在区间[1,56]循环
		if (++inext  >= 56) inext  = 1;
		if (++inextp >= 56) inextp = 1;

		retVal = SeedArray [inext] - SeedArray [inextp];    //相减而生成新随机数

		if (retVal < 0) retVal += MBIG; //确保随机数在范围之内

		SeedArray [inext] = retVal;

		return retVal * (1.0 / MBIG);
	}
	/**
	 * 返回非负随机数。
	 * Returns: 大于或等于零且小于 int.max 的 32 位带符号整数。
	 */
	public int next ()
	{
		return cast(int)(sample() * int.max);
	}
	/**
	 * 返回一个小于所指定最大值的非负随机数。
	 * Params: maxValue = 要生成的随机数的上界（随机数不能取该上界值）。
     *         maxValue = 必须大于或等于零。
     * Returns: 大于或等于零且小于 maxValue 的 32 位带符号整数，即：返回的值范围属于区间[0, maxValue)。
	 */
	public int next (int maxValue)
	in
	{
		assert(maxValue >= 0);
	}
	out(result)
	{
	    assert(result >= 0 && result < maxValue);
	}
	body
	{
		return cast(int)(sample() * maxValue);
	}
	/**
	 * 返回一个指定范围内的随机数。
	 * Params: minValue = 返回的随机数的下界（随机数可取该下界值）。
	 *         maxValue = 返回的随机数的上界（随机数不能取该上界值）。
	 *         maxValue 必须大于或等于 minValue。
	 * Returns: 一个大于或等于 minValue 且小于 maxValue 的 32 位带符号整数，即：返回的值范围属于区间[minValue, maxValue)。
	 *          如果 minValue 等于 maxValue，则返回 minValue。
	 */
	public int next (int minValue, int maxValue)
	in
	{
		assert(minValue <= maxValue);
	}
	out(result)
	{
		assert(result >= minValue && result <= maxValue);
	}
	body
	{
	    long range = cast(long)maxValue - minValue;
	    if(range <= cast(long)int.max)
	    {
	        return ( (cast(int)(sample() * range)) + minValue );
	    }
	    else
	    {
	        //对于大范围数值来说，sample()所返回的值分布还不够好
	        int result = cast(int)(sample() * MBIG);
	        if((cast(int)(sample() * MBIG)) % 2 == 0) result = -result;
	        double d = result;
	        d += int.max - 1;
	        d /= 2*cast(uint)int.max - 1;
	        return cast(int)( (cast(long)(d * range)) + minValue );
	    }
	}
	/**
	 * 用随机数填充指定字节数组的元素。
	 * Params: buffer = 包含随机数的字节数组。
	 * Comments: 字节数组的每个元素均设置为一个大于或等于零而小于或等于 int.max 的随机数。
	 */
	public void nextBytes (ubyte [] buffer)
	in
	{
		assert(buffer !is null);
		assert(buffer.length > 0);
	}
	body
	{
		for (int i = 0; i < buffer.length; i++)
		{
			buffer [i] = cast(ubyte)(sample()  * (ubyte.max + 1));
		}
	}
	/**
	 * 返回一个介于 0.0 和 1.0 之间的随机数。
	 * Returns: 大于或等于 0.0 而小于 1.0 的双精度浮点数字。
	 * Comments: 此方法是受保护的方法 Sample 的公共版本。
     */
	public double nextDouble ()
	{
		return sample();
	}
}

unittest
{
    Random random = new Random();
    ubyte[] buffer = new ubyte[100];
    random.nextBytes(buffer);
    for(int i = 0; i < buffer.length; i++)
    {
        assert( (buffer[i] >= 0) && (buffer[i] <= ubyte.max));
    }
    for(int i = 0; i < 1000; i++)
    {
        int numeric = random.next();
        assert((numeric >= 0) && ( numeric< int.max));
    }
    for(int i = 0; i < 1000; i++)
    {
        double numeric = random.nextDouble();
        assert((numeric >= 0.0) && (numeric< 1.0));
    }
}

